package com.longge;

public class IsSubtree {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        return dfs(root, subRoot);
    }

    private boolean dfs(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (root.val == subRoot.val) {
            boolean b = check(root, subRoot);
            if (b) return true;
        }
        return dfs(root.left, subRoot) || dfs(root.right, subRoot);
    }

    private boolean check(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root!=null&&subRoot!=null){
            if (root.val!=subRoot.val) return false;
        }
        if (root==null||subRoot==null) return false;
        return check(root.left,subRoot.left)&&check(root.right,subRoot.right);


    }

}
